package 力扣面试经典150;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-03-24
 * Time:14:41
 */

/**
 * 力扣面试经典150:114. 二叉树展开为链表
 * 中等
 * 相关标签
 * 相关企业
 * 提示
 * 给你二叉树的根结点 root ，请你将它展开为一个单链表：
 *     展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
 *     展开后的单链表应该与二叉树 先序遍历 顺序相同。
 * 示例 1：
 * 输入：root = [1,2,5,3,4,null,6]
 * 输出：[1,null,2,null,3,null,4,null,5,null,6]
 */
public class flatten {
    public static void main(String[] args) {
        // 创建二叉树 [1,2,5,3,4,null,6]
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(6);
        flatten(root);
    }
    public static void flatten(TreeNode root) {
        if (root == null) {
            return;
        }

        TreeNode left = root.left;
        TreeNode right = root.right;

        // 将左子树置为空，右子树指向原先的左子树
        root.left = null;
        root.right = left;

        // 找到原先右子树的最右节点
        TreeNode p = root;
        while (p.right != null) {
            p = p.right;
        }

        // 将原先右子树的最右节点指向原先的右子树
        p.right = right;

        // 递归处理左右子树
        flatten(root.right);
    }
}
